package com.LeeCode;

import java.util.Arrays;

/**
 * 火柴拼正方形
 */

public class Code473 {
    public static void main(String[] args) {
        int[] matchsticks = {3, 3, 3, 3, 4};
        System.out.println(new Code473().makesquare(matchsticks));
    }

    public boolean makesquare(int[] matchsticks) {
        if (matchsticks.length < 4) return false;

        int sum = Arrays.stream(matchsticks).sum();
        if (sum % 4 != 0) return false;

        int sideLength = sum / 4;

        // 检查最大火柴棒
        int maxStick = Arrays.stream(matchsticks).max().orElse(0);
        if (maxStick > sideLength) return false;

        // 降序排序
        Arrays.sort(matchsticks);
        reverse(matchsticks);

        return backtrack(matchsticks, new int[4], 0, sideLength);
    }

    private boolean backtrack(int[] matchsticks, int[] sides, int index, int target) {
        if (index == matchsticks.length) {
            return true; // 所有火柴棒都已成功放置
        }

        for (int i = 0; i < 4; i++) {
            // 剪枝1：超过边长
            if (sides[i] + matchsticks[index] > target) continue;

            // 剪枝2：避免重复（相同长度的边）
            if (i > 0 && sides[i] == sides[i - 1]) continue;

            // 选择
            sides[i] += matchsticks[index];

            // 递归
            if (backtrack(matchsticks, sides, index + 1, target)) {
                return true;
            }

            // 回溯
            sides[i] -= matchsticks[index];
        }

        return false;
    }

    private void reverse(int[] arr) {
        for (int i = 0; i < arr.length / 2; i++) {
            int temp = arr[i];
            arr[i] = arr[arr.length - 1 - i];
            arr[arr.length - 1 - i] = temp;
        }
    }
}
